home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / snippet.exe / PERMUTE1.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-07  |  3.4 KB  |  113 lines
  1. #include<stdio.h>
  2.  
  3. /*  chouse_n ( char *strng, int length) returns a pointer to a string of   */
  4. /*  length characters chosen from "strng" , duplicate chars in "strng" are */
  5. /*  significant.  Strings are generated in lexical order.                  */
  6. /*  First call, call with *strng. each subsiquent call, call with NULL,    */
  7. /*  returns one combination. Calls after all combinations have been        */
  8. /*  returned return NULL.  Will return NULL for errors.                    */
  9. /*  not very defensive (i.e. WILL BREAK)                                   */
  10.  
  11. /*  dave chapman aug '91  released to public domain                        */
  12.  
  13. char *chouse_n( char *strng, int length);
  14.  
  15. char *chouse_n( char *strng, int length)
  16. {
  17.       static char *str;
  18.       static char *curr;
  19.       static char *pos;       /* for each char in curr(ent string),
  20.                                  its pos in str                            */
  21.       static int  counts[256];
  22.       int i,j;
  23.  
  24.       if (0 >= length)
  25.             return NULL;
  26.  
  27.       if (NULL != strng)
  28.       {
  29.             str = malloc(strlen(strng)); /* first call, prep string for use */
  30.             curr = malloc(2 * length + 1);
  31.             pos = curr + length +1;
  32.  
  33.             for (i = 0; i < 256; counts[i++] = 0)
  34.                   ;
  35.             for (i = 0; strng[i]; i++)
  36.                   counts[strng[i]]++;
  37.  
  38.             for (i = 1, j = 0; i < 256; i++)
  39.             {
  40.                   if (counts[i])
  41.                   {
  42.                         str[j] = i;
  43.                         counts[j++] = counts[i];
  44.                   }
  45.             }
  46.             str[j] = '\0';      /* str is string of distinct chars in order */
  47.                                 /* counts[] holds count of each char        */
  48.  
  49.             /* take first length chars */
  50.  
  51.             for (i = 0,j = 0; i < length; i++)
  52.             {
  53.                   curr[i] = str[j];
  54.                   pos[i] = j;
  55.                   if (!(--counts[j]))
  56.                         j++;
  57.             }
  58.             curr[i] = '\0';
  59.             return curr;
  60.       }
  61.       /* if called with "mississippi",5;
  62.          str -> "imps"
  63.          curr -> "iiiim"
  64.          counts -> 0,0,2,4;
  65.          pos -> 0,0,0,0,1;   */
  66.       
  67.       /* go back to front */
  68.  
  69.       for (j = length; j > 0;)
  70.       {
  71.             counts[ pos[--j]]++;                      /* "replace" char */
  72.  
  73.             /* look for a new char for curr posit. */
  74.  
  75.             for ( i = ++pos[j]; str[i] && ! counts[i]; i++);
  76.             if (curr[j] = str[i])                     /* found a char   */
  77.             {
  78.                   --counts[i];
  79.                   pos[j] = i;
  80.  
  81.                   /* placed char, fill out rest of string  */
  82.  
  83.                   for (++j, i = 0; j < length; j++)
  84.                   {
  85.                         for ( ; !counts[i]; i++)
  86.                               ;
  87.                         curr[j] = str[i];       /* first available char */
  88.                         --counts[i];
  89.                         pos[j] = i;
  90.                   }
  91.                   return curr;
  92.             }
  93.             /* no more chars for this pos ; go back one */
  94.       }
  95.       /*  done */
  96.       return NULL;
  97. }
  98.  
  99. void main(void)
  100. {
  101.       char  *str = "aabbccdd";
  102.       int i,j;
  103.  
  104.       j = 0;
  105.       i =  5;
  106.       puts(chouse_n( str, i));
  107.       while (str = chouse_n(NULL, i))
  108.       {
  109.             ++j;
  110.             printf(" %s  %d\n",str,j);
  111.       }
  112. }
  113.